"""
1. 堆一般采用完全二叉树
2. 堆中的每一个节点都大于其左右子节点（大顶堆），
或者堆中每一个节点都小于其左右子节点（小顶堆）
"""


class Heap(object):
    def __init__(self):
        # 初始化一个空堆
        self.data_list = []

    # 获取父节点的下标
    def get_parent_index(self, index):
        # 判断下标是否越界
        if index == 0 or index > len(self.data_list) - 1:
            return None
        else:
            # 二进制位移动
            return (index - 1) >> 1

    # 交换结点
    def swap(self, index_a, index_b):
        self.data_list[index_a], self.data_list[index_b] = self.data_list[index_b], self.data_list[index_a]

    # 添加结点
    def insert(self, data):
        # 先追加到数组的最后
        self.data_list.append(data)
        # 插入结点的下标
        index = len(self.data_list) - 1
        # 获取父节点下标
        parent = self.get_parent_index(index)
        while parent is not None and self.data_list[parent] < self.data_list[index]:
            # 交换
            self.swap(parent, index)
            index = parent
            parent = self.get_parent_index(parent)

    # 删除堆顶元素
    def remove_max(self):
        # 删除堆顶元素，然后将最后一个元素放在堆顶，再从上往下依次堆化
        remove_data = self.data_list[0]
        self.data_list[0] = self.data_list[-1]
        del self.data_list[-1]

        # 堆化
        self.heapify(0)
        return remove_data

    # 堆化
    def heapify(self, index):
        # 从上往下堆化，从 index 开始堆化操作 (大顶堆)
        total_index = len(self.data_list) - 1
        while True:
            maxvalue_index = index
            if 2 * index + 1 <= total_index and self.data_list[2 * index + 1] > self.data_list[maxvalue_index]:
                maxvalue_index = 2 * index + 1
            if 2 * index + 2 <= total_index and self.data_list[2 * index + 2] > self.data_list[maxvalue_index]:
                maxvalue_index = 2 * index + 2
            if maxvalue_index == index:
                break
            self.swap(index, maxvalue_index)
            index = maxvalue_index
















